﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GameLibrary.AI.Knapsack
{
    public static class KnapsackHelper
    {
        #region sort item
        internal static void SortItem(int[] pj, int[] wj, out int[] p, out int[] w, out List<KeyValuePair<int, int>> mapList)
        {
            p = new int[pj.GetLength(0)];
            w = new int[wj.GetLength(0)];

            mapList = new List<KeyValuePair<int, int>>();
            for (int i = 0; i < pj.GetLength(0); i++)
                mapList.Add(new KeyValuePair<int, int>(i, pj[i] / wj[i]));
            mapList.Sort(new SortItemComparer());
            int count = 0;
            foreach (var i in mapList)
            {
                p[count] = pj[i.Key];
                w[count] = wj[i.Key];
                count++;
            }
        }
        class SortItemComparer : IComparer<KeyValuePair<int, int>>
        {
            #region IComparer<KeyValuePair<int,double>> Members

            public int Compare(KeyValuePair<int, int> x, KeyValuePair<int, int> y)
            {
                return y.Value.CompareTo(x.Value);
            }

            #endregion
        }
        internal static void GetOriginalSequance(List<KeyValuePair<int, int>> mapList, int[] x, out int[] xj)
        {
            xj = new int[8];
            for (int i = 0; i < 8; i++)
                if (x[i] == 1)
                    xj[mapList[i].Key] = 1;
        }
        #endregion
        #region critical_item
        /*
         *          
         * Source:
         *      Knapsack Problems: Algorithms and Computer Implementations by Silvano Martello and Paolo Toth
         *      page: 18
         * 
         * procedure CRITICAL_ITEM
         * input: n, c, (pj), (wj);
         * output: s;
         * 
         * begin
         * |     J1 := null;
         * |     J0 := null;
         * |     JC := {1,...,n}
         * |     _c := c;
         * |     partition := "no"
         * |     while partition = "no" do
         * |        begin
         * |        |   determine the median lamda of the values in R = { pj/wj : j belong to JC};
         * |        |   G := { j belong to JC: pj/wj > lamda}
         * |        |   L := { j belong to JC: pj/wj < lamda}
         * |        |   E := { j belong to JC: pj/wj = lamda}
         * |        |   c' := sum[j belong to G] wj
         * |        |   c'' := c' + sum]j belong to E] wj;
         * |        |   if c' <= _c < c'' then partition = "yes"
         * |        |   else if c' > _c then (comment: lamda is too small)
         * |        |           begin
         * |        |           |   J0 := J0 union L union E;
         * |        |           |   JC := G;
         * |        |           end
         * |        |       else (comment: lamda is too large)
         * |        |           begin
         * |        |           |   J1 := J1 union G union E;
         * |        |           |   JC := L;
         * |        |           |   _c := _c -  c'';
         * |        |           end
         * |        end
         * |    J1 := J1 union G
         * |    J0 := J0 union L
         * |    JC := E ( = {e1,...,eq} )
         * |    _c = _c-c'
         * |    delta = min{ j: sum[i=1toj] wei > _c};
         * |    s := edelta
         * end
         * 
         * 
         */
        /// <summary>
        /// return citical position in sorted list
        /// require all item arranged by p1/w1 >= p2/w2 >= ... >= pn/wn
        /// </summary>
        /// <param name="n"></param>
        /// <param name="c"></param>
        /// <param name="pj"></param>
        /// <param name="wj"></param>
        /// <param name="dic"></param>
        /// <param name="s"></param>
        /// <returns></returns>
        public static void CRITICAL_ITEM(
            //input
            int n, // item number
            int c, // knapsack capacity
            int[] pj, // profit of item j
            int[] wj, // weight of item j
            List<KeyValuePair<int,int>> mapList,
            //output
            out int s // critical item number
            )
        {
            HashSet<int> J1 = new HashSet<int>();
            HashSet<int> J0 = new HashSet<int>();
            HashSet<int> JC = new HashSet<int>();
            for (int i = 0; i < n; i++)
                JC.Add(i);
            int _c = c;
            YesNo partition = YesNo.no;
            int[] r = mapList.Select(kv=>kv.Value).ToArray();
            HashSet<int> G = null;
            HashSet<int> E = null;
            HashSet<int> L = null;
            int cqout = 0;
            while (partition == YesNo.no)
            {
                int lamda = GetSum(r,JC) / n;
                E = GetE(JC, mapList, lamda);
                G = GetG(JC, mapList, lamda);
                L = GetL(JC, mapList, lamda);
                cqout = GetSum(wj, G);
                int cqoutqout = cqout + GetSum(wj, E);
                if (cqout <= _c && _c < cqoutqout)
                    partition = YesNo.yes;
                else
                    if (cqout > _c)
                    {
                        J0.UnionWith(L);
                        J0.UnionWith(E);
                        JC = G;
                    }
                    else
                    {
                        J1.UnionWith(G);
                        J1.UnionWith(E);
                        JC = L;
                        _c = _c - cqoutqout;
                    }
            }
            J1.UnionWith(G);
            J0.UnionWith(L);
            JC = E;
            _c = _c - cqout;
            
            int delta = GetMinPosition(E, _c, wj);
            s = E.ElementAt(delta);
        }
        /// <summary>
        /// j belong to JC : pj/wj &gt lamda
        /// </summary>
        /// <param name="set"></param>
        /// <param name="Dictionary"></param>
        /// <param name="lamda"></param>
        /// <returns></returns>
        internal static HashSet<int> GetG(HashSet<int> set, List<KeyValuePair<int,int>> maplist, int lamda)
        {
            HashSet<int> G = new HashSet<int>();
            for (int i = set.First(); i <=set.Last(); i++)
                if (maplist[i].Value > lamda)
                    G.Add(i);
            return G;
        }
        /// <summary>
        /// j belong to JC : pj/wj == lamda
        /// </summary>
        /// <param name="set"></param>
        /// <param name="Dictionary"></param>
        /// <param name="lamda"></param>
        /// <returns></returns>
        internal static HashSet<int> GetE(HashSet<int> set, List<KeyValuePair<int,int>> maplist, int lamda)
        {
            HashSet<int> E = new HashSet<int>();
            for (int i = set.First(); i <=set.Last(); i++)
            {
                if (maplist[i].Value == lamda)
                    E.Add(i);
            }
            return E;
        }
        /// <summary>
        /// j belong to JC : pj/wj &lt lamda
        /// </summary>
        /// <param name="set"></param>
        /// <param name="Dictionary"></param>
        /// <param name="lamda"></param>
        /// <returns></returns>
        internal static HashSet<int> GetL(HashSet<int> set, List<KeyValuePair<int,int>> maplist, int lamda)
        {
            HashSet<int> L = new HashSet<int>();
            for (int i = set.Last(); i >= set.First(); i--)
            {
                if (maplist[i].Value < lamda)
                    L.Add(i);
            }
            return L;
        }
        /// <summary>
        /// Sum all array element appared in set.
        /// </summary>
        /// <param name="array"></param>
        /// <param name="set"></param>
        /// <returns></returns>
  /*      internal static double GetSum(double[] array, HashSet<int> set)
        {
            double total = 0;
            foreach (var a in set)
                total += array[a];
            return total;
        }
   */ 
        internal static int GetSum(int[] array, HashSet<int> set)
        {
            int total = 0;
            foreach (var a in set)
                total += array[a];
            return total;
        }
        /// <summary>
        /// min { j : sum[i = 1 to j] wei < _C}
        /// </summary>
        /// <param name="set"></param>
        /// <param name="value"></param>
        /// <param name="array"></param>
        /// <returns></returns>
        internal static int GetMinPosition(HashSet<int> set, int value, int[] array)
        {
            List<int> list = new List<int>(set);
            for (int i = 0; i < list.Count; i++)
            {
                int total = 0;
                for (int j = 0; j <= i; j++)
                    total += array[list[j]];
                if (total > value)
                {
                    return i;
                }
            }
            throw new Exception(" Should not reach.");
        }
        #endregion

    }
}
